package top.interview.string

import problem.Problem

import scala.annotation.tailrec

class Q125ValidPalindrome extends Problem {
  def isPalindrome(s: String): Boolean = {
    isPalindrome(s.toLowerCase, 0, s.length - 1)
  }

  @tailrec
  final def isPalindrome(s: String, l: Int, r: Int): Boolean = {
    //    println(s.substring(l, r + 1))
    if (l >= r) true
    else if (!s(l).isLetterOrDigit) isPalindrome(s, l + 1, r)
    else if (!s(r).isLetterOrDigit) isPalindrome(s, l, r - 1)
    else if (s(l) == s(r)) isPalindrome(s, l + 1, r - 1)
    else false
  }

  override def test(): Unit = {
    isPalindrome("A man, a plan, a canal: Panama") shouldBe true
    isPalindrome("race a car") shouldBe false
  }
}
